LeetCode 538、把二叉搜索树转换为累加树

一、题目描述

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

二、题目解析

三、参考代码

// 作者：程序员吴师兄
// 网站：https://www.algomooc.com
class Solution {
 
    // 定义一个变量，用来记录已经访问的所有节点值的总和
    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        
        // 1、从根节点开始，修改二叉树上的每一个节点的值
        modify(root);

        // 返回修改后的二叉树的根节点
        return root;
    }

    // 按照右根左的顺序，遍历二叉树上的每一个节点，将每个节点的值累加到 sum 上面
    // 同时把 sum 累加到当前节点上
    private void modify(TreeNode node ){

        // 如果当前节点为空，那么就不需要计算了
        if(node == null) return ;

        // 2、去修改当前节点的右子树上面的节点
        // 修改的过程中，会不断的累加当前节点右子树上所有的节点值之和
        modify(node.right);

        // 3、把当前节点右子树上所有的节点值之和在加上当前节点的值更新到 sum 上
        sum += node.val;

        // 4、 修改当前节点的值为 sum
        node.val = sum;

        // 5、去修改当前节点的左子树上面的节点
        // 修改的过程中，会不断的累加当前节点左子树上所有的节点值之和
        modify(node.left);
    }
}